package com.wuxuan.algorithm_homework.stackAndQueue;

import java.util.*;

/**
 * 括号匹配
 *
 * 给定一个只包括'('，')'，'{'，'}，'[',  ']'的字符串s，判断字符串是否有效。有效字符串需满足:
 * 左括号必须用相同类型的右括号闭合，
 * 左括号必须以正确的顺序闭合。
 * 每个右括号都有一个对应的相同类型的左括号。
 */
public class Q3 {

    //Deque（双端队列）在功能上集合了队列和栈的特点，是一种非常灵活的数据结构。
    // 它允许你在队列的两端（头部和尾部）进行插入和删除操作，这使得它可以用来实现队列、栈，甚至其他更复杂的数据结构操作。

    //时间复杂度：O(n)， n为字符串的长度
    //空间复杂度：O(n)， n为字符串的长度
    public boolean isValid(String s) {
        if (s.length() % 2 == 1) {
            return false;
        }
        Map<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('{', '}');
        map.put('[', ']');

        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                stack.offerLast(c);
                //???:这个不是用equals比较准确吗？？？
                //答：在Java中，对于基本数据类型（如 char），使用 == 是完全正确的。== 用于比较基本数据类型时，是比较它们的值是否相等。
                //在你的代码中，c 是一个 char 类型的变量，map.get(stack.peekLast()) 也返回一个 char 类型的值。因此，使用 == 是合适的。
                //如果你使用的是对象类型（如 Character/String），则需要使用 equals 方法来比较它们的值是否相等，因为 == 会比较对象的引用是否相同。

                //基本数据类型（如 char、int、double 等）：
                //使用 == 比较它们的值是否相等。

                //对象类型（如 Character、String、Integer 等）：
                //使用 == 比较它们的引用是否相同。
                //使用 equals 方法比较它们的值是否相等。
            } else if (!stack.isEmpty() && c == map.get(stack.peekLast())) {
                stack.pollLast();
            } else {
                return false;
            }
        }
        return stack.isEmpty();
    }
}
